package leetcode;


//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
//你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。



/*
   解法：
   1、暴力穷举
      目标是找到当前值的另一个值，即target - cur。对于数组中的每个值，遍历其后的所有值，寻找target - cur
      时间复杂度： O(n^2)
      空间复杂度： O(1)
   2、hash表
      遍历数组。查看hash表中是否存在target - cur，如果存再，返回hash表的存在的值，如果不存在，将当前值和位置存放在hash表中。
      时间复杂度： O(n)
      空间复杂度： O(n)
    思考：
        怎么才能把空间利用的更高效？
        hash表需要存储两个值，一个是具体的值，一个是索引。int数组可以表示两个值，但是不知道数组申请多长。

 */

import java.util.HashMap;
import java.util.Map;

public class Code1 {


    public int[] twoSum(int[] nums, int target) {
        //<target- cur, index>
        if(nums == null || nums.length <=0){
            throw new IllegalArgumentException("No two sum solution");
        }

        Map<Integer, Integer> targetIndex = new HashMap<>(nums.length);

        for(int i=0; i<nums.length ;i++){
            int cur = nums[i];
            int other = target - cur;
            if(targetIndex.containsKey(other)){
                return new int[]{targetIndex.get(other), i};
            }else{
                targetIndex.put(cur, i);
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
